{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #判断二分图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isBipartite"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断二分图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>存在一个 <strong>无向图</strong> ，图中有 <code>n</code> 个节点。其中每个节点都有一个介于 <code>0</code> 到 <code>n - 1</code> 之间的唯一编号。</p>\n",
    "\n",
    "<p>给定一个二维数组 <code>graph</code>&nbsp;，表示图，其中 <code>graph[u]</code> 是一个节点数组，由节点 <code>u</code> 的邻接节点组成。形式上，对于&nbsp;<code>graph[u]</code> 中的每个 <code>v</code> ，都存在一条位于节点 <code>u</code> 和节点 <code>v</code> 之间的无向边。该无向图同时具有以下属性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>不存在自环（<code>graph[u]</code> 不包含 <code>u</code>）。</li>\n",
    "\t<li>不存在平行边（<code>graph[u]</code> 不包含重复值）。</li>\n",
    "\t<li>如果 <code>v</code> 在 <code>graph[u]</code> 内，那么 <code>u</code> 也应该在 <code>graph[v]</code> 内（该图是无向图）</li>\n",
    "\t<li>这个图可能不是连通图，也就是说两个节点 <code>u</code> 和 <code>v</code> 之间可能不存在一条连通彼此的路径。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>二分图</strong> 定义：如果能将一个图的节点集合分割成两个独立的子集 <code>A</code> 和 <code>B</code> ，并使图中的每一条边的两个节点一个来自 <code>A</code> 集合，一个来自 <code>B</code> 集合，就将这个图称为 <strong>二分图</strong> 。</p>\n",
    "\n",
    "<p>如果图是二分图，返回 <code>true</code><em> </em>；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/21/bi2.jpg\" style=\"width: 222px; height: 222px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2,3],[0,2],[0,1,3],[0,2]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong><code>不能将节点分割成两个独立的子集，</code>以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/21/bi1.jpg\" style=\"width: 222px; height: 222px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,3],[0,2],[1,3],[0,2]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong><code>可以将节点分成两组: {0, 2} 和 {1, 3} 。</code></pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>graph.length == n</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= graph[u].length &lt; n</code></li>\n",
    "\t<li><code>0 &lt;= graph[u][i] &lt;= n - 1</code></li>\n",
    "\t<li><code>graph[u]</code> 不会包含 <code>u</code></li>\n",
    "\t<li><code>graph[u]</code> 的所有值 <strong>互不相同</strong></li>\n",
    "\t<li>如果 <code>graph[u]</code> 包含 <code>v</code>，那么 <code>graph[v]</code> 也会包含 <code>u</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 785&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/is-graph-bipartite/\">https://leetcode-cn.com/problems/is-graph-bipartite/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [vEAB3K](https://leetcode.cn/problems/vEAB3K/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [vEAB3K](https://leetcode.cn/problems/vEAB3K/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[0,2],[0,1,3],[0,2]]', '[[1,3],[0,2],[1,3],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        default, left, right = 0, -1, 1\n",
    "        color = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if color[i] == default:\n",
    "                q = deque([i])\n",
    "                color[i] = left\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    change = right if color[node] == left else left\n",
    "                    for j in graph[node]:\n",
    "                        if color[j] == default:\n",
    "                            color[j] = change\n",
    "                            q.append(j)\n",
    "                        elif color[j] != change:\n",
    "                            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        classes = [0] * n\n",
    "        visited = [False] * n\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                q = deque([i])\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    visited[x] = True\n",
    "                    for y in graph[x]:\n",
    "                        if not visited[y]:\n",
    "                            classes[y] = 1 - classes[x]\n",
    "                            q.append(y)\n",
    "                        else:\n",
    "                            if classes[y] != 1 - classes[x]:\n",
    "                                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        self.len = len(graph)\n",
    "        colors = [-1 for _ in range(self.len)]\n",
    "        for i in range(self.len):\n",
    "            if colors[i]<0 and not self.dfs(i, graph, colors, 0):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def dfs(self, idx, graph, colors, color):\n",
    "        if colors[idx]>0:\n",
    "            return colors[idx]==color\n",
    "        else:\n",
    "            colors[idx] = color\n",
    "            for i in graph[idx]:\n",
    "                if not self.dfs(i, graph, colors, 1-color):\n",
    "                    return False\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        m = len(graph)\n",
    "        visited = [0]*m\n",
    "        q = deque()\n",
    "        for i in range(m):\n",
    "            if visited[i] != 0:\n",
    "                continue\n",
    "            visited[i] = 1\n",
    "            q.append(i)\n",
    "            while q:\n",
    "                c = q.popleft()\n",
    "                for e in graph[c]:\n",
    "                    if visited[c] == visited[e]:\n",
    "                        return False\n",
    "                    if visited[e] == 0:\n",
    "                        visited[e] = -visited[c]\n",
    "                        q.append(e)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, g: List[List[int]]) -> bool:\n",
    "        n = len(g)\n",
    "        parent = [i for i in range(n)]\n",
    "        def find(x):\n",
    "            if x != parent[x]:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x, y):\n",
    "            root1, root2 = find(x), find(y)\n",
    "            parent[root1] = root2\n",
    "        def issame(x, y):\n",
    "            return find(x) == find(y)\n",
    "            \n",
    "        for x, neri in enumerate(g):\n",
    "            for y in neri:\n",
    "                if issame(x, y):\n",
    "                    return False\n",
    "                union(y, neri[0])\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 主函数，输入邻接表，判断是否是二分图\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # 记录图是否符合二分图性质\n",
    "        self.ok = True\n",
    "        # 记录图中节点的颜色，False和True代表两种不同颜色\n",
    "        self.color = []\n",
    "        # 记录图中节点是否被访问过\n",
    "        self.visited = []\n",
    "\n",
    "        n = len(graph)\n",
    "        self.color = [False] * n\n",
    "        self.visited = [False] * n\n",
    "        # 因为图不一定是联通的，可能存在多个子图\n",
    "        # 所以要把每个节点都作为起点进行一次遍历\n",
    "        # 如果发现任何一个子图不是二分图，整幅图都不算二分图\n",
    "        for v in range(n):\n",
    "            if not self.visited[v]:\n",
    "                self.traverse(graph, v)\n",
    "                if not self.ok:\n",
    "                    return False # 如果已经确定不是二分图了，就不用浪费时间再遍历了\n",
    "        return self.ok\n",
    "\n",
    "    # DFS 遍历框架\n",
    "    def traverse(self, graph: List[List[int]], v: int) -> None:\n",
    "        self.visited[v] = True\n",
    "        for w in graph[v]:\n",
    "            if not self.visited[w]:\n",
    "                # 相邻节点 w 没有被访问过\n",
    "                # 那么应该给节点 w 涂上和节点 v 不同的颜色\n",
    "                self.color[w] = not self.color[v]\n",
    "                # 继续遍历 w\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                # 相邻节点 w 已经被访问过\n",
    "                # 根据 v 和 w 的颜色判断是否是二分图\n",
    "                if self.color[w] == self.color[v]:\n",
    "                    # 若相同，则此图不是二分图\n",
    "                    self.ok = False\n",
    "                    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ok = True\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        visited = [False] * n\n",
    "        colors = [False] * n\n",
    "\n",
    "        # # DFS\n",
    "        # def dfs(graph, x):\n",
    "        #     visited[x] = True\n",
    "\n",
    "        #     for w in graph[x]:\n",
    "        #         if visited[w]:\n",
    "        #             if colors[w] == colors[x]:\n",
    "        #                 self.ok = False\n",
    "        #                 return\n",
    "        #         else:\n",
    "        #             colors[w] = True if not colors[x] else False\n",
    "        #             dfs(graph, w)\n",
    "            \n",
    "        # for v in range(n):\n",
    "        #     if not visited[v]:\n",
    "        #         dfs(graph, v)\n",
    "\n",
    "\n",
    "        # BFS\n",
    "        def bfs(graph, x):\n",
    "            q = [x]\n",
    "            while q and self.ok:\n",
    "                v = q.pop()\n",
    "                visited[v] = True\n",
    "                for w in graph[v]:\n",
    "                    if visited[w]:\n",
    "                        if colors[w] == colors[v]:\n",
    "                            self.ok = False\n",
    "                            return\n",
    "                    else:\n",
    "                        colors[w] = True if not colors[v] else False\n",
    "                        visited[w] = True\n",
    "                        q.append(w)\n",
    "        for v in range(n):\n",
    "            if not visited[v]:\n",
    "                bfs(graph, v)\n",
    "        return self.ok"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        visited = [0] * n\n",
    "        for i in range(n):\n",
    "            if visited[i]:\n",
    "                continue\n",
    "            visited[i] = 1\n",
    "            q = [i]\n",
    "            while q:\n",
    "                nxt = []\n",
    "                for t in q:\n",
    "                    for node in graph[t]:\n",
    "                        if not visited[node]:\n",
    "                            visited[node] = 2 if visited[t] == 1 else 1\n",
    "                            nxt.append(node)\n",
    "                        elif visited[node] == visited[t]:\n",
    "                            return False\n",
    "                q = nxt\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        d = {i: -1 for i in range(len(graph))}\n",
    "        for u in range(len(graph)):\n",
    "            if d[u]==-1:\n",
    "                d[u], l = 0, [u]\n",
    "                while l:\n",
    "                    x = l.pop()\n",
    "                    for v in graph[x]:\n",
    "                        if d[v]==-1: \n",
    "                            d[v] = 1^d[x]\n",
    "                            l.append(v)\n",
    "                        elif d[v] != 1^d[x]: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                q = collections.deque([i])\n",
    "                color[i] = RED\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    cNei = (GREEN if color[node] == RED else RED)\n",
    "                    for neighbor in graph[node]:\n",
    "                        if color[neighbor] == UNCOLORED:\n",
    "                            color[neighbor] = cNei\n",
    "                            q.append(neighbor)\n",
    "                        elif color[neighbor] != cNei:\n",
    "                            return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        colors = [0] * n  # 0表示未染色，1和-1表示两种不同的颜色\n",
    "\n",
    "        for i in range(n):\n",
    "            if colors[i] == 0:  # 未染色的节点\n",
    "                queue = []\n",
    "                queue.append(i)\n",
    "                colors[i] = 1  # 染成第一种颜色\n",
    "\n",
    "                while queue:\n",
    "                    node = queue.pop(0)\n",
    "                    for neighbor in graph[node]:\n",
    "                        if colors[neighbor] == 0:  # 未染色的邻居节点\n",
    "                            colors[neighbor] = -colors[node]  # 染成不同的颜色\n",
    "                            queue.append(neighbor)\n",
    "                        elif colors[neighbor] == colors[node]:\n",
    "                            return False  # 如果邻居节点已经染成了相同的颜色，说明不是二分图\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # 构建遍历函数\n",
    "        self.ok = True\n",
    "        self.color = [False] * len(graph)\n",
    "        self.visited = [False] * len(graph) \n",
    "        def traverse(graph, s):\n",
    "            if not self.ok:\n",
    "                return \n",
    "            self.visited[s] = True\n",
    "            for v in graph[s]:\n",
    "                if not self.visited[v]:\n",
    "                    self.color[v] = not self.color[s]\n",
    "                    traverse(graph, v)\n",
    "                else:\n",
    "                    if self.color[v] == self.color[s]:\n",
    "                        self.ok = False\n",
    "                        return\n",
    "        for i in range(len(graph)):\n",
    "            if not self.visited[i]:\n",
    "                traverse(graph, i)\n",
    "                if not self.ok:\n",
    "                    break\n",
    "        return self.ok\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        colors = [0 for _ in range(n)]\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            if colors[i] != 0:\n",
    "                continue\n",
    "            colors[i] = 1 # 染色\n",
    "            queue.append(i)\n",
    "            while queue:\n",
    "                idx = queue.popleft()\n",
    "                color = colors[idx]\n",
    "                for node in graph[idx]:\n",
    "                    if colors[node] == 0:\n",
    "                        colors[node] = -color\n",
    "                        queue.append(node)\n",
    "                    elif colors[node] == color:\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        valid = True\n",
    "        assign_lst = [0] * n\n",
    "        \n",
    "        # def dfs(vert, assign_val):\n",
    "        #     nonlocal valid\n",
    "        #     if valid:\n",
    "        #         if assign_lst[vert] == 0:\n",
    "        #             assign_lst[vert] = assign_val\n",
    "        #             for n_vert in graph[vert]:\n",
    "        #                 dfs(n_vert, -assign_val)\n",
    "        #         elif assign_lst[vert] != assign_val:\n",
    "        #             valid = False\n",
    "\n",
    "        # for vert, assign_val in enumerate(assign_lst):\n",
    "        #     if assign_val == 0:\n",
    "        #         dfs(vert, 1)\n",
    "        #         if not valid:\n",
    "        #             return valid\n",
    "        # return valid\n",
    "\n",
    "        # bfs\n",
    "        for vert, assign_val in enumerate(assign_lst):\n",
    "            if assign_val == 0:\n",
    "                assign_lst[vert] = 1\n",
    "                q = collections.deque([vert])\n",
    "                while q:\n",
    "                    curr_vert = q.popleft()\n",
    "                    curr_assign_val = -assign_lst[curr_vert]\n",
    "                    for n_vert in graph[curr_vert]:\n",
    "                        if assign_lst[n_vert] == 0:\n",
    "                            assign_lst[n_vert] = curr_assign_val\n",
    "                            q.append(n_vert)\n",
    "                        elif assign_lst[n_vert] != curr_assign_val:\n",
    "                            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNVISITED, GREEN, RED = 0, 1, 2\n",
    "        visited = [UNVISITED]*n\n",
    "\n",
    "        for i in range(n):\n",
    "            if visited[i] == UNVISITED:\n",
    "                q = collections.deque([i])\n",
    "                visited[i] = RED\n",
    "\n",
    "            while q:\n",
    "                node = q.popleft()\n",
    "                cNei = (GREEN if visited[node] == RED else RED)\n",
    "                for neibor in graph[node]:\n",
    "                    if visited[neibor] == UNVISITED:\n",
    "                        visited[neibor] = cNei\n",
    "                        q.append(neibor)\n",
    "                    elif visited[neibor] != cNei:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UnionFinder:\n",
    "    def __init__(self, n):\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.rank = [0 for i in range(n)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x == self.root[x]:\n",
    "            return x\n",
    "        \n",
    "        rootX = self.find(self.root[x])\n",
    "        self.root[x] = rootX\n",
    "        return rootX\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX == rootY:\n",
    "            return\n",
    "        \n",
    "        if self.rank[rootX] > self.rank[rootY]:\n",
    "            self.rank[rootX] += 1\n",
    "            self.root[rootY] = rootX\n",
    "        else:\n",
    "            self.rank[rootY] += 1\n",
    "            self.root[rootX] = rootY\n",
    "\n",
    "    def isConnect(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        uf = UnionFinder(n)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                if uf.isConnect(i, j):\n",
    "                    return False\n",
    "                uf.union(graph[i][0], j)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "        for i in range(n):\n",
    "            if color[i] == 0:\n",
    "                color[i] = 1\n",
    "                q = deque([i])\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in graph[x]:\n",
    "                        if color[y] == 0 :\n",
    "                            color[y] = -color[x]\n",
    "                            q.append(y)\n",
    "                        elif color[y] == color[x]:\n",
    "                            return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                q = collections.deque([i])\n",
    "                color[i] = RED\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    cNei = (GREEN if color[node] == RED else RED)\n",
    "                    for neighbor in graph[node]:\n",
    "                        if color[neighbor] == UNCOLORED:\n",
    "                            q.append(neighbor)\n",
    "                            color[neighbor] = cNei\n",
    "                        elif color[neighbor] != cNei:\n",
    "                            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                q = collections.deque([i])\n",
    "                color[i] = RED\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    cNei = (GREEN if color[node] == RED else RED)\n",
    "                    for neighbor in graph[node]:\n",
    "                        if color[neighbor] == UNCOLORED:\n",
    "                            q.append(neighbor)\n",
    "                            color[neighbor] = cNei\n",
    "                        elif color[neighbor] != cNei:\n",
    "                            return False\n",
    "\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        part = [-1] * n\n",
    "        for i in range(n):\n",
    "            if part[i] != -1:\n",
    "                continue\n",
    "            q, head = [i], -1\n",
    "            part[i] = 0\n",
    "            while head < len(q) - 1:\n",
    "                head += 1\n",
    "                u = q[head]\n",
    "                for v in graph[u]:\n",
    "                    if part[v] == -1:\n",
    "                        part[v] = 1 - part[u]\n",
    "                        q.append(v)\n",
    "                    elif part[v] != 1 - part[u]:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        colors = [0 for _ in range(n)]\n",
    "        queue = deque()\n",
    "        for i in range(n):\n",
    "            if colors[i] != 0:\n",
    "                continue\n",
    "            colors[i] = 1 # 染色\n",
    "            queue.append(i)\n",
    "            while queue:\n",
    "                idx = queue.popleft()\n",
    "                color = colors[idx]\n",
    "                for node in graph[idx]:\n",
    "                    if colors[node] == 0:\n",
    "                        colors[node] = -color\n",
    "                        queue.append(node)\n",
    "                    elif colors[node] == color:\n",
    "                        return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        valid = True\n",
    "        assign_lst = [0] * n\n",
    "        \n",
    "        def dfs(vert, assign_val):\n",
    "            nonlocal valid\n",
    "            if valid:\n",
    "                if assign_lst[vert] == 0:\n",
    "                    assign_lst[vert] = assign_val\n",
    "                    for n_vert in graph[vert]:\n",
    "                        dfs(n_vert, -assign_val)\n",
    "                elif assign_lst[vert] != assign_val:\n",
    "                    valid = False\n",
    "\n",
    "        for vert, assign_val in enumerate(assign_lst):\n",
    "            if assign_val == 0:\n",
    "                dfs(vert, 1)\n",
    "                if not valid:\n",
    "                    return valid\n",
    "        return valid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#用递归的方法通过了，但是时间复杂度和内存都不小\n",
    "#但是由于这是递归回溯的方法，貌似只能用递归\n",
    "#能想到的优化手段，就是一次添加一个点和其邻接点，而不是一次一条边\n",
    "\n",
    "#如果以连通思维的话，就是深度和广度优先遍历\n",
    "#广度写了，再来一个深度的\n",
    "\n",
    "# def isB(set1,set2,list1):\n",
    "#     if len(list1)==0:\n",
    "#         return True\n",
    "#     else:\n",
    "#         flag=True\n",
    "#         l,r=list1[0]\n",
    "#         l1,l2=l in set1, l in set2\n",
    "#         r1,r2=r in set1, r in set2\n",
    "#         if l1:\n",
    "#             if r1:\n",
    "#                 return False\n",
    "#             elif not r2:\n",
    "#                 set2.add(r)\n",
    "\n",
    "#         elif l2:\n",
    "#             if r2:\n",
    "#                 return False\n",
    "#             elif not r1:\n",
    "#                 set1.add(r)\n",
    "#         else:\n",
    "#             if r1:\n",
    "#                 set2.add(l)\n",
    "#             elif r2:\n",
    "#                 set1.add(l)\n",
    "#             else:\n",
    "#                 flag=False\n",
    "#         if flag:\n",
    "#             return isB(set1,set2,list1[1:])\n",
    "#         else:\n",
    "#             sset1=set1 | {l}\n",
    "#             sset2=set2 | {r}\n",
    "#             sset3=set1 | {r}\n",
    "#             sset4=set2 | {l}\n",
    "#             return isB(sset1,sset2,list1[1:]) or isB(sset3,sset4,list1[1:])\n",
    "\n",
    "\n",
    "def isB(i,graph,colors): \n",
    "    for j in graph[i]:\n",
    "        if colors[j]==-1:\n",
    "            colors[j]=1-colors[i]\n",
    "            if not isB(j,graph,colors):\n",
    "                return False \n",
    "        else:\n",
    "            if colors[j]==colors[i]:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        colors=[-1 for i in range(len(graph))]\n",
    "        for i in range(len(graph)):\n",
    "            if colors[i]==-1:\n",
    "                colors[i]=0\n",
    "                if not isB(i,graph,colors):\n",
    "                    return False\n",
    "        return True\n",
    "                \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "\n",
    "    def add(self, x: str):\n",
    "        self.parent[x] = x\n",
    "        self.size[x] = 1\n",
    "        self.cnt += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        # 小的树挂到大的树上， 使树尽量平衡\n",
    "        leader_p = self.find(p)\n",
    "        leader_q = self.find(q)\n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "        self.cnt -= 1\n",
    "\n",
    "\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        uf = UF()\n",
    "        for i in range(n):\n",
    "            uf.add(i)\n",
    "\n",
    "        for u in range(n):\n",
    "            edges = graph[u]\n",
    "            for i, v in enumerate(edges):\n",
    "                if i == 0:\n",
    "                    leader = v\n",
    "                    continue \n",
    "                uf.union(leader, v)\n",
    "                if uf.connected(u, v): return False\n",
    "        \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "        for i in range(n):\n",
    "            if color[i] == 0:\n",
    "                color[i] = 1\n",
    "                q = deque()\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in graph[x]:\n",
    "                        if color[y] == color[x]:\n",
    "                            return False\n",
    "                        elif color[y] == 0:\n",
    "                            color[y] = -color[x]\n",
    "                            q.append(y)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def traverse(self, node, graph):\n",
    "        if self.visited[node]:\n",
    "            return\n",
    "        \n",
    "        self.visited[node] = True\n",
    "        self.q.append(node)\n",
    "        while self.q:\n",
    "            for _ in range(len(self.q)):\n",
    "                node = self.q.popleft()\n",
    "                for neighbor in graph[node]:\n",
    "                    if self.visited[neighbor]:\n",
    "                        if self.color[node] == self.color[neighbor]:\n",
    "                            self.ok = False\n",
    "                            return\n",
    "                    else:\n",
    "                        self.color[neighbor] = not self.color[node]\n",
    "                        self.visited[neighbor] = True\n",
    "                        self.q.append(neighbor)\n",
    "\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        self.q = collections.deque()\n",
    "        self.visited = [False] * len(graph)\n",
    "        self.color = [False] * len(graph)\n",
    "        self.ok = True\n",
    "\n",
    "        for node in range(len(graph)):\n",
    "            if not self.visited[node]:\n",
    "                self.traverse(node, graph)\n",
    "                if not self.ok:\n",
    "                    return self.ok\n",
    "        \n",
    "        return self.ok\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "def bfs(node, graph, arrive):\n",
    "        q = deque()\n",
    "        q.append(node)\n",
    "        color = 1\n",
    "        arrive[node] = color\n",
    "        while len(q) > 0:\n",
    "            node = q.popleft()\n",
    "            color = 0 - arrive[node]\n",
    "            for n in graph[node]:\n",
    "                if n not in arrive:\n",
    "                    q.append(n)\n",
    "                    arrive[n] = color\n",
    "                elif arrive[n] != color: \n",
    "                    return False\n",
    "        return True\n",
    "        \n",
    "class Solution:\n",
    "            \n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        arrive = dict()\n",
    "        while len(arrive) < len(graph):\n",
    "            # 找到一个没访问的点\n",
    "            for i, _ in enumerate(graph):\n",
    "                if i not in arrive:\n",
    "                    node = i\n",
    "                    break\n",
    "            if not bfs(node, graph, arrive):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        seen = [0] * n\n",
    "        nodes = deque()\n",
    "        cur = 1\n",
    "        for i in range(n):\n",
    "            if not seen[i]:\n",
    "                nodes.append(i)\n",
    "                seen[i] = cur                \n",
    "                while nodes:\n",
    "                    cur = -cur\n",
    "                    for _ in range(len(nodes)):\n",
    "                        node = nodes.popleft()\n",
    "                        for j in graph[node]:\n",
    "                            if not seen[j]:\n",
    "                                nodes.append(j)\n",
    "                                seen[j] = cur\n",
    "                            else:\n",
    "                                if seen[j] != cur:\n",
    "                                    return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        vis = [0]*n\n",
    "        q = collections.deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if not vis[i]:\n",
    "                q.append(i)\n",
    "                vis[i]=1\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    color = vis[node]\n",
    "                    for child in graph[node]:\n",
    "                        if vis[child]==color:\n",
    "                            return False\n",
    "                        if not vis[child]:\n",
    "                            vis[child]=-color\n",
    "                            q.append(child)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        self.success = True\n",
    "        self.graph = graph\n",
    "        n = len(graph)\n",
    "        self.visited = [False] * n\n",
    "        self.color = [False] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            if not self.visited[i]:\n",
    "                self.dfs_traverse(i)\n",
    "        \n",
    "        return self.success\n",
    "\n",
    "    def dfs_traverse(self, v):\n",
    "        if not self.success:\n",
    "            return\n",
    "        \n",
    "        self.visited[v] = True\n",
    "\n",
    "        for w in self.graph[v]:\n",
    "            if self.visited[w]:\n",
    "                if self.color[w] == self.color[v]:\n",
    "                    self.success = False\n",
    "                    return \n",
    "            else:\n",
    "                self.color[w] = not self.color[v]\n",
    "                self.dfs_traverse(w)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, size: int):\n",
    "        self.pa = [i for i in range(size)]\n",
    "        self.size = [1] * size\n",
    "\n",
    "    def search(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.search(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.search(x), self.search(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.pa[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = graph.__len__()\n",
    "        dsu = Dsu(n)\n",
    "        for i in range(n):\n",
    "            for j in graph[i]:\n",
    "                dsu.union(i, j)\n",
    "        islands = list(set(dsu.pa))\n",
    "        node_dict = dict()\n",
    "        # bfs\n",
    "        q = deque(islands)\n",
    "        while q:\n",
    "            current = q.popleft()\n",
    "            if current in node_dict:\n",
    "                continue\n",
    "            adj = 'C'\n",
    "            # search nearby\n",
    "            for adjacent in graph[current]:\n",
    "                if adjacent not in node_dict:\n",
    "                    q.append(adjacent)\n",
    "                    continue\n",
    "                if adj == 'C':\n",
    "                    adj = node_dict[adjacent]\n",
    "                else:\n",
    "                    if adj != node_dict[adjacent]:\n",
    "                        return False\n",
    "            if adj == 'A':\n",
    "                node_dict[current] = 'B'\n",
    "            else:\n",
    "                node_dict[current] = 'A'\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, g: List[List[int]]) -> bool:\n",
    "        N = len(g)\n",
    "        C = [ -1 for _ in range(N+1) ]\n",
    "\n",
    "        def check(p):\n",
    "            C[p] = 0\n",
    "            Q = deque([ (p, 0) ])\n",
    "            while Q:\n",
    "                u, c = Q.popleft()\n",
    "                nextc = 1 - c\n",
    "                for v in g[u]:\n",
    "                    if C[v] == c:\n",
    "                        return False\n",
    "                    if C[v] != nextc:\n",
    "                        C[v] = nextc\n",
    "                        Q.append((v, nextc))\n",
    "            return True\n",
    "        \n",
    "        for i in range(N):\n",
    "            if C[i] == -1:\n",
    "                if not check(i):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        pa = [i for i in range(n)]\n",
    "        rank = [1 for _ in range(n)]\n",
    "\n",
    "        def find(u):\n",
    "            if u==pa[u]:\n",
    "                return pa[u]\n",
    "            else:\n",
    "                pa[u] = find(pa[u])\n",
    "                return pa[u]\n",
    "        \n",
    "        def union(u,v):\n",
    "            u,v = find(u),find(v)\n",
    "            if rank[u]<=rank[v]:\n",
    "                pa[u]=v\n",
    "            else:\n",
    "                pa[v]=u\n",
    "            if rank[u]==rank[v] and u!=v:\n",
    "                rank[v]+=1\n",
    "        \n",
    "        def isconnected(u,v):\n",
    "            return find(u)==find(v)\n",
    "\n",
    "        for u,children in enumerate(graph):\n",
    "            for child in children:\n",
    "                if isconnected(u, child):\n",
    "                    return False\n",
    "                union(child,children[0])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        colors = [0] * n  # 记录每个节点的颜色，0表示未染色，1表示红色，-1表示蓝色\n",
    "\n",
    "        for i in range(n):\n",
    "            if colors[i] == 0 and not self.dfs(graph, colors, i, 1):\n",
    "                return False\n",
    "\n",
    "        return True\n",
    "\n",
    "    def dfs(self, graph, colors, node, color):\n",
    "        colors[node] = color\n",
    "\n",
    "        for neighbor in graph[node]:\n",
    "            if colors[neighbor] == color:\n",
    "                return False  # 如果相邻节点的颜色与当前节点相同，则说明不是二分图\n",
    "            elif colors[neighbor] == 0 and not self.dfs(graph, colors, neighbor, -color):\n",
    "                return False  # 如果相邻节点未染色，递归染色并检查是否满足条件\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n=len(graph)\n",
    "        kkk=setUnion(n)\n",
    "        for arr in graph:\n",
    "            for i in range(1,len(arr)):\n",
    "                kkk.union(arr[0],arr[i])\n",
    "        for i,arr in enumerate(graph):\n",
    "            for v in arr:\n",
    "                if kkk.is_connected(i,v): return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        div = ['' for _ in range(len(graph))]\n",
    "\n",
    "        currGroup = True\n",
    "        queue = deque([])\n",
    "        for t in range(len(div)):\n",
    "            if div[t] == '':\n",
    "                queue.append(t)\n",
    "                while queue:\n",
    "                    for i in range(len(queue)):\n",
    "                        index = queue.popleft()\n",
    "                        if currGroup and div[index] == 'v': return False\n",
    "                        if not currGroup and div[index] == 'u': return False\n",
    "                        div[index] = 'u' if currGroup else 'v'\n",
    "                        for j in graph[index]:\n",
    "                            if div[j] == '': queue.append(j)\n",
    "                    currGroup = not currGroup\n",
    "\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n=len(graph)\n",
    "        visited=[0]*n\n",
    "        q=[]\n",
    "        for i in range(n):\n",
    "            if visited[i]!=0:\n",
    "                continue\n",
    "            else:\n",
    "                q.append(i)\n",
    "                visited[i]=1\n",
    "            while q:\n",
    "                temp=q.pop(0)\n",
    "                for g in graph[temp]:\n",
    "                    if visited[g]==visited[temp]:\n",
    "                        return False\n",
    "                    if visited[g]==0:\n",
    "                        visited[g]=-visited[temp]\n",
    "                        q.append(g)\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n= len(graph)\n",
    "        colors = [ -1 for i in range(n)]\n",
    "        RED = 0\n",
    "        BLUE = 1\n",
    "        \n",
    "        def bfs(node):\n",
    "            q = deque()\n",
    "            q.append(node)\n",
    "            \n",
    "            colors[node] = RED\n",
    "            while q:\n",
    "                tmp = q.popleft()\n",
    "                for v in graph[tmp]:\n",
    "                    if colors[v] == colors[tmp]:\n",
    "                        return False\n",
    "                    elif colors[v] == 1 - colors[tmp]:\n",
    "                        continue\n",
    "                    else:\n",
    "                        colors[v] = 1 - colors[tmp]\n",
    "                        q.append(v)\n",
    "            return True\n",
    "        \n",
    "        for i in range(n):\n",
    "            if colors[i] == -1:\n",
    "                if bfs(i) == False:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        color = [0] * len(graph)\n",
    "        for i in range(len(graph)):\n",
    "            if color[i] == 0:\n",
    "                q = collections.deque([i])\n",
    "                color[i] = 1\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    cNei = 1 if color[node] == 2 else 2\n",
    "                    for j in graph[node]:\n",
    "                        if color[j] == 0:\n",
    "                            q.append(j)\n",
    "                            color[j] = cNei\n",
    "                        elif color[j] != cNei:\n",
    "                            return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.visted = []\n",
    "        self.color = []\n",
    "        self.ok = True\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        self.visted = [False] * n\n",
    "        self.color = [False] * n\n",
    "\n",
    "        for v in range(n):\n",
    "            if not self.visted[v]:\n",
    "                self.traverse(graph, v)\n",
    "                if not self.ok:\n",
    "                    break\n",
    "        return self.ok\n",
    "    def traverse(self, graph, v):\n",
    "        self.visted[v] = True\n",
    "        for w in graph[v]:\n",
    "            if not self.visted[w]:\n",
    "                self.color[w] = not self.color[v]\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                if self.color[w] == self.color[v]:\n",
    "                    self.ok = False\n",
    "                    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n=len(graph)\n",
    "        s1=set()\n",
    "        s2=set()\n",
    "        for j in range(n):\n",
    "            que=deque([j])\n",
    "            while len(que)>0:\n",
    "                i=que.popleft()\n",
    "                if i in s1:\n",
    "                    for num in graph[i]:\n",
    "                        if num not in s1 and num not in s2:\n",
    "                            s2.add(num)\n",
    "                            que.append(num)\n",
    "                        elif num in s1:\n",
    "                            return False\n",
    "                        else:\n",
    "                            continue\n",
    "                elif i in s2:\n",
    "                    for num in graph[i]:\n",
    "                        if num not in s1 and num not in s2:\n",
    "                            s1.add(num)\n",
    "                            que.append(num)\n",
    "                        elif num in s2:\n",
    "                            return False\n",
    "                        else:\n",
    "                            continue\n",
    "                else:\n",
    "                    flag1,flag2=False,False\n",
    "                    for num in graph[i]:\n",
    "                        if num in s1:\n",
    "                            flag1=True\n",
    "                        if num in s2:\n",
    "                            flag2=True\n",
    "                    if flag1==True and flag2==True:\n",
    "                        return False\n",
    "                    elif flag1==True and flag2==False:\n",
    "                        s1.add(i)\n",
    "                    else:\n",
    "                        s2.add(i)\n",
    "                    if i in s1:\n",
    "                        for num in graph[i]:\n",
    "                            if num not in s2:\n",
    "                                s2.add(num)\n",
    "                                que.append(num)\n",
    "                            else:\n",
    "                                continue\n",
    "                    else:\n",
    "                        for num in graph[i]:\n",
    "                            if num not in s1:\n",
    "                                s1.add(num)\n",
    "                                que.append(num)\n",
    "                            else:\n",
    "                                continue      \n",
    "        return True\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n=len(graph)\n",
    "        color=[0]*n\n",
    "        def dfs(i:int,c:int) -> bool:\n",
    "            nonlocal color\n",
    "            color[i]=c\n",
    "            for j in graph[i]:\n",
    "                if color[j]==0:\n",
    "                    if not dfs(j,3-c):\n",
    "                        return False\n",
    "                elif color[j]==c:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if color[i]==0:\n",
    "                if not dfs(i,1):\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        pa = [i for i in range(n)]\n",
    "        rank = [1 for _ in range(n)]\n",
    "\n",
    "        def find(u):\n",
    "            if u==pa[u]:\n",
    "                return pa[u]\n",
    "            else:\n",
    "                pa[u] = find(pa[u])\n",
    "                return pa[u]\n",
    "        \n",
    "        def union(u,v):\n",
    "            u,v = find(u),find(v)\n",
    "            if rank[u]<=rank[v]:\n",
    "                pa[u]=v\n",
    "            else:\n",
    "                pa[v]=u\n",
    "            if rank[u]==rank[v] and u!=v:\n",
    "                rank[v]+=1\n",
    "        \n",
    "        def isconnected(u,v):\n",
    "            return find(u)==find(v)\n",
    "\n",
    "        for u,children in enumerate(graph):\n",
    "            for child in children:\n",
    "                if isconnected(u, child):\n",
    "                    return False\n",
    "                union(child,children[0])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ok = True\n",
    "        self.visited = []\n",
    "        self.color = []\n",
    "    \n",
    "    def traverse(self, graph, v):\n",
    "        if not self.ok:\n",
    "            return\n",
    "        self.visited[v] = True\n",
    "\n",
    "        for w in graph[v]:\n",
    "            if not self.visited[w]:\n",
    "                self.color[w] = not self.color[v]\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                if self.color[w] == self.color[v]:\n",
    "                    self.ok = False\n",
    "                    return\n",
    "        \n",
    "\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        self.visited = [False] * n\n",
    "        self.color = [False] * n\n",
    "\n",
    "        for v in range(n):\n",
    "            self.traverse(graph, v)\n",
    "            if not self.ok:\n",
    "                return self.ok\n",
    "        return self.ok\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        colors = {}\n",
    "        g=graph\n",
    "\n",
    "        def dfs(node, c):\n",
    "            for nxt in g[node]:\n",
    "                if nxt in colors and colors[nxt]==c:\n",
    "                    return False\n",
    "                elif nxt not in colors:\n",
    "                    colors[nxt]=1-c\n",
    "                    if not dfs(nxt,1-c):\n",
    "                        return False\n",
    "            return True\n",
    "        for i in range(len(g)):\n",
    "            if i not in colors:\n",
    "                colors[i]=0\n",
    "                if not dfs(i,0):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self):\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.cnt = 0\n",
    "\n",
    "    def add(self, x: str):\n",
    "        self.parent[x] = x\n",
    "        self.size[x] = 1\n",
    "        self.cnt += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "        return x\n",
    "\n",
    "    def union(self, p, q):\n",
    "        if self.connected(p, q): return\n",
    "        # 小的树挂到大的树上， 使树尽量平衡\n",
    "        leader_p = self.find(p)\n",
    "        leader_q = self.find(q)\n",
    "        if self.size[leader_p] < self.size[leader_q]:\n",
    "            self.parent[leader_p] = leader_q\n",
    "            self.size[leader_q] += self.size[leader_p]\n",
    "        else:\n",
    "            self.parent[leader_q] = leader_p\n",
    "            self.size[leader_p] += self.size[leader_q]\n",
    "        self.cnt -= 1\n",
    "\n",
    "\n",
    "    def connected(self, p, q):\n",
    "        return self.find(p) == self.find(q)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        uf = UF()\n",
    "        for i in range(n):\n",
    "            uf.add(i)\n",
    "\n",
    "        for u in range(n):\n",
    "            edges = graph[u]\n",
    "            for i, v in enumerate(edges):\n",
    "                if i == 0:\n",
    "                    leader = v\n",
    "                    continue \n",
    "                uf.union(leader, v)\n",
    "                if uf.connected(u, v): return False             # 任何边的两个顶点 u, v 不能够在同一集合\n",
    "        \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def DFS(self,graph,root,bOrw,color):\n",
    "        #print('root=',root,bOrw)\n",
    "        if bOrw[root]==-1:\n",
    "            bOrw[root] = color\n",
    "            for nxt in graph[root]:\n",
    "                if self.DFS(graph,nxt,bOrw,1-color)==False:\n",
    "                    return False\n",
    "            return True\n",
    "        elif bOrw[root]!=color:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        bOrw= [-1] * n\n",
    "        for i in range(n):\n",
    "            if bOrw[i]!=-1:\n",
    "                continue\n",
    "            bOrw[i] = 1\n",
    "            for root in  graph[i]:\n",
    "                if bOrw[root]==1:\n",
    "                    return False\n",
    "            \n",
    "                if self.DFS(graph,root,bOrw,0)==False:\n",
    "                    return False\n",
    "        \n",
    "       \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-03a72/er-fen-tu--73400/\n",
    "# 说白了就是遍历一遍图，一边遍历一边染色，看看能不能用两种颜色给所有节点染色，且相邻节点的颜色都不相同。\n",
    "# DFS 遍历框架\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 记录图是否符合二分图性质\n",
    "        self.ok = True\n",
    "        # 记录图中节点是否被访问过\n",
    "        self.visited = None\n",
    "        # 记录图中节点的颜色，false 和 true 代表两种不同颜色\n",
    "        self.color = None\n",
    "\n",
    "    # 主函数，输入邻接表，判断是否是二分图\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # 初始化init里面的参数\n",
    "        self.visited = [False] * len(graph)\n",
    "        self.color = [False] * len(graph)\n",
    "\n",
    "        # 因为图不一定是联通的，可能存在多个子图\n",
    "        # 所以要把每个节点都作为起点进行一次遍历\n",
    "        # 如果发现任何一个子图不是二分图，整幅图都不算二分图\n",
    "        for i in range(len(graph)):\n",
    "            # 这里相当于剪枝，不写这个if其实也可以\n",
    "            if not self.visited[i]:\n",
    "                self.traverse(graph, i)\n",
    "\n",
    "        return self.ok\n",
    "    \n",
    "    # DFS 遍历框架\n",
    "    def traverse(self, graph, s):\n",
    "        # 如果已经确定不是二分图了，就不用浪费时间再递归遍历了\n",
    "        if not self.ok:\n",
    "            return\n",
    "        \n",
    "        self.visited[s] = True\n",
    "        for w in graph[s]:\n",
    "            if not self.visited[w]:\n",
    "                # 相邻节点 w 没有被访问过\n",
    "                # 那么应该给节点 w 涂上和节点 v 不同的颜色\n",
    "                # self.visited[w] = True # 这句不要写，因为下面有递归，递归的时候就会赋值为true了\n",
    "                self.color[w] = not self.color[s]\n",
    "                # 继续遍历 w\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                # 相邻节点 w 已经被访问过\n",
    "                # 根据 v 和 w 的颜色判断是否是二分图\n",
    "                if self.color[w] == self.color[s]:\n",
    "                    self.ok = False\n",
    "                    return\n",
    "                else:\n",
    "                    continue\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        size = len(graph)\n",
    "        colors = [-1] * size\n",
    "        for i in range(size):\n",
    "            if colors[i] == -1:\n",
    "                if not set_color(graph, colors, i, 0):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "def set_color(graph, colors, i, color):\n",
    "    q = []\n",
    "    q.append(i)\n",
    "    colors[i] = color\n",
    "    while q:\n",
    "        v = q.pop()\n",
    "        for _, ni in enumerate(graph[v]):\n",
    "            if colors[ni] >= 0:\n",
    "                if colors[ni] == colors[v]:\n",
    "                    return False\n",
    "            else:\n",
    "                q.append(ni)\n",
    "                colors[ni] = 1 - colors[v]\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ok = True\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        visited = [False] * n\n",
    "        colors = [False] * n\n",
    "\n",
    "        # BFS\n",
    "        def dfs(graph, x):\n",
    "            visited[x] = True\n",
    "\n",
    "            for w in graph[x]:\n",
    "                if visited[w]:\n",
    "                    if colors[w] == colors[x]:\n",
    "                        self.ok = False\n",
    "                        return\n",
    "                else:\n",
    "                    colors[w] = True if not colors[x] else False\n",
    "                    dfs(graph, w)\n",
    "            \n",
    "        for v in range(n):\n",
    "            if not visited[v]:\n",
    "                dfs(graph, v)\n",
    "        return self.ok"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        s = [None] * n\n",
    "\n",
    "        def dsf(x, f):\n",
    "            if s[x] is not None and s[x] != f:\n",
    "                return False\n",
    "            \n",
    "            if s[x] == f:\n",
    "                return True\n",
    "\n",
    "            s[x] = f\n",
    "            for v in graph[x]:\n",
    "                if not dsf(v, not f):\n",
    "                    return False\n",
    "            return True\n",
    "        f = True\n",
    "        for i in range(n):\n",
    "            if s[i] is not None:\n",
    "                continue\n",
    "            if not dsf(i, True):\n",
    "                return False\n",
    "            \n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # bfs的过程中对节点进行染色，同一条边的2端的节点需要有不同的颜色\n",
    "        # 如果遍历到发现某个节点已经被染色，且与将要染上的颜色不同，则不是二分图\n",
    "        n = len(graph)\n",
    "        color = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if not self.bfs(graph, color, i):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def bfs(self, graph: List[List[int]], color: List[int], start_i: int) -> bool:\n",
    "        if color[start_i] != 0:\n",
    "            return True\n",
    "\n",
    "        color[start_i] = 1\n",
    "        next_node_list = deque([start_i])\n",
    "        while len(next_node_list) > 0:\n",
    "            cur_node = next_node_list.popleft()\n",
    "\n",
    "            for next_node in graph[cur_node]:\n",
    "                # 是否已经涂色\n",
    "                if color[next_node] == color[cur_node]:\n",
    "                    return False\n",
    "                if color[next_node] != 0:\n",
    "                    continue\n",
    "                color[next_node] = color[cur_node] * -1\n",
    "                next_node_list.append(next_node)\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        groups = [-1]*n\n",
    "        visited = set()\n",
    "\n",
    "        def dfs(idx, group):\n",
    "            visited.add(idx)\n",
    "            groups[idx] = group\n",
    "            group = 1 - group\n",
    "            for nei in graph[idx]:\n",
    "                if nei in visited:\n",
    "                    if groups[nei] != group:\n",
    "                        return False\n",
    "                else:\n",
    "                    if not dfs(nei, group):\n",
    "                        return False\n",
    "            \n",
    "            return True\n",
    "\n",
    "        for idx in range(n):\n",
    "            if idx not in visited:\n",
    "                if not dfs(idx, 0):\n",
    "                    return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        if len(graph) == 0:\n",
    "            return False\n",
    "\n",
    "        colors = [-1] * len(graph)\n",
    "\n",
    "        def dfs(node, c):\n",
    "            colors[node] = c\n",
    "            next_c = 2 if c == 1 else 1\n",
    "\n",
    "            for neibor in graph[node]:\n",
    "                if colors[neibor] == -1:\n",
    "                    if not dfs(neibor, next_c):\n",
    "                        return False\n",
    "                elif colors[neibor] == c:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        \n",
    "        for i in range(len(graph)):\n",
    "            if colors[i] == -1:\n",
    "                if(not dfs(i, 1)):\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        visited = {}\n",
    "        self.valid = True\n",
    "        \n",
    "\n",
    "        if len(graph) == 0:\n",
    "            return True\n",
    "\n",
    "        def dfs(node: int, previous_color):            \n",
    "            if node not in visited:\n",
    "                previous_color = 1 - previous_color\n",
    "                visited[node] = previous_color\n",
    "\n",
    "            for neighbor in graph[node]:\n",
    "                if neighbor in visited:\n",
    "                    if visited[node] == visited[neighbor]:\n",
    "                        self.valid = False\n",
    "                        return \n",
    "                    continue\n",
    "\n",
    "                dfs(neighbor, previous_color)\n",
    "        \n",
    "        for node in range(len(graph)):\n",
    "            dfs(node, 0)\n",
    "        \n",
    "        return self.valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        colors = [-1] * n\n",
    "\n",
    "        @cache\n",
    "        def dfs(node,color):\n",
    "            colors[node] = color\n",
    "            for neighbor in graph[node]:\n",
    "                if colors[neighbor] == color:\n",
    "                    return False\n",
    "                if colors[neighbor] == -1 and not dfs(neighbor,1 - color):\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        for i in range (n):\n",
    "            if colors[i] == -1 and not dfs(i,0):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "        \n",
    "        def dfs(node, c):\n",
    "            color[node] = c\n",
    "            cNei = 1 if c == 2 else 2\n",
    "            for p in graph[node]:\n",
    "                if color[p] == 0:\n",
    "                    if not dfs(p, cNei):\n",
    "                        return False\n",
    "                elif color[p] != cNei:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if color[i] == 0:\n",
    "                if not dfs(i, 1):\n",
    "                    return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        valid = True\n",
    "\n",
    "        def dfs(node, c):\n",
    "            nonlocal valid\n",
    "            color[node] = c\n",
    "            cNei = (GREEN if c == RED else RED)\n",
    "            for neighbor in graph[node]:\n",
    "                if color[neighbor] == UNCOLORED:\n",
    "                    dfs(neighbor, cNei)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif color[neighbor] != cNei:\n",
    "                    valid = False\n",
    "                    return\n",
    "        \n",
    "\n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                dfs(i, RED)\n",
    "                if not valid:\n",
    "                    break\n",
    "        \n",
    "        return valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # 无向图\n",
    "        # 0代表未染色，1代表一种颜色，-1代表另外一种颜色\n",
    "        color = [0]*len(graph)\n",
    "        \n",
    "        def dfs(i):\n",
    "            for nxt in graph[i]:\n",
    "                if color[nxt] == 0:\n",
    "                    color[nxt] = -color[i]\n",
    "                    if not dfs(nxt):\n",
    "                        return False\n",
    "                else:\n",
    "                    if color[nxt] == color[i]:\n",
    "                        return False \n",
    "            return True \n",
    "        \n",
    "        for i in range(len(color)):\n",
    "            if color[i] == 0:\n",
    "                color[i] = 1\n",
    "                if not dfs(i):\n",
    "                    return False \n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        has = [0] * n\n",
    "        def dfs(x,c):\n",
    "            has[x] = c\n",
    "            for i in graph[x]:\n",
    "                if has[i] == c or (has[i] == 0 and dfs(i,-c)):\n",
    "                    return True\n",
    "            return False\n",
    "        for i in range(n):\n",
    "            if has[i] == 0 and dfs(i,1): return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        valid = True\n",
    "\n",
    "        def dfs(node: int, c: int):\n",
    "            nonlocal valid\n",
    "            color[node] = c\n",
    "            cNei = (GREEN if c == RED else RED)\n",
    "            for neighbor in graph[node]:\n",
    "                if color[neighbor] == UNCOLORED:\n",
    "                    dfs(neighbor, cNei)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif color[neighbor] != cNei:\n",
    "                    valid = False\n",
    "                    return\n",
    "\n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                dfs(i, RED)\n",
    "                if not valid:\n",
    "                    break\n",
    "        \n",
    "        return valid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        colors = [-1] * len(graph)\n",
    "\n",
    "        def dfs(node, c):\n",
    "            colors[node] = c\n",
    "            next_c = 2 if c == 1 else 1\n",
    "\n",
    "            for neibor in graph[node]:\n",
    "                if colors[neibor] == -1:\n",
    "                    if not dfs(neibor, next_c):\n",
    "                        return False\n",
    "                elif colors[neibor] == c:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        \n",
    "        for i in range(len(graph)):\n",
    "            if colors[i] == -1:\n",
    "                if(not dfs(i, 1)):\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        from collections import defaultdict\n",
    "        g=graph\n",
    "        c=[-1]*len(g)\n",
    "        def dfs(x,color):\n",
    "            c[x]=color\n",
    "            for i in g[x]:\n",
    "                if c[i]==-1:\n",
    "                    dfs(i,1-color)\n",
    "        for i in range(len(g)):\n",
    "            if c[i]==-1:\n",
    "                dfs(i,0)\n",
    "        for i in range(len(g)):\n",
    "            for j in g[i]:\n",
    "                if c[i]==c[j]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        n = len(graph)\n",
    "        color = [UNCOLORED] * n\n",
    "\n",
    "        def dfs(node: int, c: int) -> bool:\n",
    "            color[node] = c\n",
    "            cNei = GREEN if c == RED else RED\n",
    "            for neighbor in graph[node]:\n",
    "                if color[neighbor] == UNCOLORED:\n",
    "                    if not dfs(neighbor, cNei):\n",
    "                        return False\n",
    "                elif color[neighbor] != cNei:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                if not dfs(i, RED):\n",
    "                    return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        init, red, blue = 0, 1, 2\n",
    "        valid = True\n",
    "        node_color = {i: init for i in range(n)}\n",
    "        def dfs(node, color):\n",
    "            nonlocal valid\n",
    "            node_color[node] = color\n",
    "            cNei = blue if color == red else red\n",
    "            for nei in graph[node]:\n",
    "                current_color = node_color[nei]\n",
    "                if current_color == init:\n",
    "                    dfs(nei, cNei)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif current_color != cNei:\n",
    "                    valid = False\n",
    "                    return\n",
    "                \n",
    "\n",
    "        for i in range(n):\n",
    "            if node_color[i] != init:\n",
    "                continue\n",
    "            dfs(i, red)\n",
    "            if not valid:\n",
    "                return False\n",
    "        return valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        colors = [0] * n\n",
    "        GRAY = 0\n",
    "        RED = 1\n",
    "        GREEN = 2\n",
    "\n",
    "        def change_color(color: int):\n",
    "            return GREEN if color == RED else RED\n",
    "                \n",
    "        def dfs(j: int, parent_color: int) -> bool:\n",
    "            if colors[j] == GRAY:\n",
    "                colors[j] = change_color(parent_color)\n",
    "                for v in graph[j]:\n",
    "                    res = dfs(v, colors[j])\n",
    "                    if not res:\n",
    "                        return False\n",
    "                return True\n",
    "            elif colors[j] == parent_color:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        for i, targets in enumerate(graph):\n",
    "            if colors[i] == GRAY:\n",
    "                # 还未被访问\n",
    "                res = dfs(i, RED)\n",
    "                if not res:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        record = [0] * n\n",
    " \n",
    "        def dfs(point, c):\n",
    "            record[point] = c\n",
    "            for i in graph[point]:\n",
    "            # 访问为-c的点直接跳过\n",
    "                if record[i] == -c:\n",
    "                    continue\n",
    "            # 染色相同则不能为二分图\n",
    "                elif record[i] == c:\n",
    "                    return False\n",
    "            # 对于没访问过的点染色\n",
    "                elif record[i] == 0 and not dfs(i, -c):\n",
    "                    return False\n",
    "            return True\n",
    " \n",
    "        for i in range(n):\n",
    "            if record[i] == 0 and not dfs(i, 1):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.color = None\n",
    "        self.adj = []\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        nodeList = []\n",
    "        for i, neigs in enumerate(graph):\n",
    "            nodeList.append(Node(i))\n",
    "        for i, neigs in enumerate(graph):\n",
    "            for n in neigs:\n",
    "                nodeList[i].adj.append(nodeList[n])\n",
    "        for node in nodeList:\n",
    "            if node.color is None:\n",
    "                isValid = self.dfsCheck(node)\n",
    "                if not isValid:\n",
    "                    return False\n",
    "        return isValid\n",
    "    \n",
    "    def dfsCheck(self, node):\n",
    "        isValid = True\n",
    "        def dfs(node, color):\n",
    "            nonlocal isValid\n",
    "            node.color = color\n",
    "            nextColor = 0 if color else 1\n",
    "            for neig in node.adj:\n",
    "                if neig.color == color:\n",
    "                    isValid = False\n",
    "                    return\n",
    "                elif neig.color is None:\n",
    "                    dfs(neig, nextColor)\n",
    "        dfs(node, 1)\n",
    "        return isValid\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
